//给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。 
//
// 示例: 
//
// 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
//输出:
//[
//  ["ate","eat","tea"],
//  ["nat","tan"],
//  ["bat"]
//] 
//
// 说明： 
//
// 
// 所有输入均为小写字母。 
// 不考虑答案输出的顺序。 
// 
// Related Topics 哈希表 字符串 
// 👍 506 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.*;

/**
 * Java：字母异位词分组
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P49_GroupAnagrams {
    public static void main(String[] args) {
        Solution solution = new P49_GroupAnagrams().new Solution();
        MyUtil.print(solution.groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 计算唯一key
     */
//    class Solution {
//        public List<List<String>> groupAnagrams(String[] strs) {
//            List<List<String>> list = new ArrayList<>();
//            if (strs == null) {
//                return list;
//            }
//            if (strs.length == 1) {
//                List<String> subList = new ArrayList<>();
//                subList.add(strs[0]);
//                list.add(subList);
//                return list;
//            }
//
//            Map<UniqueCode, List<String>> map = new HashMap<>();
//            for (String str : strs) {
//                long add = 0;
//                long multiply = 1;
//                for (char c : str.toCharArray()) {
//                    add += c;
//                    multiply *= c;
//                }
//
//                UniqueCode key = new UniqueCode(add, multiply);
//                List<String> subList = map.get(key);
//                if (subList == null) {
//                    subList = new ArrayList<>();
//                    subList.add(str);
//                    map.put(key, subList);
//                } else {
//                    subList.add(str);
//                    map.put(key, subList);
//                }
//            }
//            map.forEach((x, y) -> list.add(y));
//            return list;
//        }
//
//        private class UniqueCode {
//            // 加
//            private long add;
//            // 乘积
//            private long multiply;
//
//            public UniqueCode(long add, long multiply) {
//                this.add = add;
//                this.multiply = multiply;
//            }
//
//            @Override
//            public boolean equals(Object obj) {
//                if (!(obj instanceof UniqueCode)) {
//                    return false;
//                }
//                UniqueCode obj1 = (UniqueCode) obj;
//                return (obj1.add == add) && (obj1.multiply == multiply);
//            }
//
//            @Override
//            public int hashCode() {
//                return (int)((add + multiply) + (add * multiply));
//            }
//        }
//    }

    /**
     * 常规解法 str排序放入map中
     */
    class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            if (strs == null) {
                return new ArrayList<>();
            }

            Map<String, List<String>> map = new HashMap<>();
            for (String str : strs) {
                char[] cs = str.toCharArray();
                Arrays.sort(cs);
                String key = new String(cs);
                // 此处经典，先初始化list后直接链式设值
                if (!map.containsKey(key)) {
                    map.put(key, new ArrayList<>());
                }
                map.get(key).add(str);
            }
            return new ArrayList<>(map.values());
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)

}